\chapter{组合论 Combinatorics}
\author{科普中国}
\date{2021-12-31}

		\section{概述}
		组合论的对象是具有组合性质的集合，以其个数的计算为主要目标。要对组合性质给予明确的定义是困难的。简单的代数系，例如序集、格、半群等的最原始的个数计算都可以看作组合论的内容，近代统计学的应用的各种布局问题、电子计算机的程序设计的组合论方面，最近也被注意，此外，概率论、分子结构、工程学等方面产生的组合问题也归入了组合论。
		
		\section{历史}
		基本的组合概念和枚举结果出现在整个古代世界。在公元前6世纪，古印度医生Sushruta在Sushruta Samhita中断言，可以从6种不同的口味中选择63种组合，一次一个，两次一组地进行，从而计算出全部$2^6-1$个可能性。希腊历史学家普鲁塔克（Plutarch）讨论了Chrysippus（公元前3世纪）和Hipparchus（公元前2世纪）之间的一个相当微妙的枚举问题，后来证明它与Schröder-Hipparchus数量有关。在Ostomachion，阿基米德（公元前3世纪）认为拼贴拼图。
		
		在中世纪，组合学继续被研究，主要在欧洲文明之外。印度数学家大雄（约850），用于数量提供式排列和组合，和这些公式可能早在第六世纪CE一直熟悉印度数学家。所述的哲学家和天文学家拉比亚伯拉罕伊本斯拉（约1140）建立的对称性二项式系数，而由后得到的封闭式的Talmudist和数学家Levi Ben Gerson（更为人所知的是Gersonides），在1321年。数学家在可追溯到10世纪的论文中提出了算术三角形 - 一个显示二项式系数之间关系的图表，并最终将成为帕斯卡的三角。后来，在中世纪的英格兰，坎帕尼学提供了一些现在称为哈密尔顿循环的例子，这些哈密尔顿循环在某些Cayley图上是排列的。
		
		在文艺复兴时期，与其他数学和科学一起，组合学享受重生。帕斯卡，牛顿，雅各布·伯努利和欧拉作品成为新兴领域基础。在现代，JJ Sylvester（19世纪末）和Percy MacMahon（20世纪初）的作品为枚举和代数组合奠定了基础。图论也同时引起了人们的兴趣，特别是在四色问题上。
		
		20世纪下半叶，组合学得到了飞速发展，形成了数十种新的学术期刊和会议。部分原因是由于从代数到概率，从功能分析到数论等其他领域的新的联系和应用，这种联系被激发出来。这些联系脱离了数学和理论计算机科学之间的组合界限，但同时也导致了该领域的局部分裂。
		
		\section{组合学的方法和子领域}
		\subsection{枚举组合}
		三个顶点上的五个二叉树，一个加泰罗尼亚数字的例子。
		
		枚举组合是组合的最经典的领域，专注于计算某些组合对象的数量。尽管统计一组元素的数量是一个相当广泛的数学问题，但是在应用程序中出现的许多问题具有相对简单的组合描述。斐波纳契数是枚举组合问题的基本例子。在12倍的方式提供用于计算一个统一的框架排列，组合和分区。
		
		\subsection{分析组合}
		分析组合学涉及使用来自复杂分析和概率理论的工具列举组合结构。与使用显式组合公式和生成函数来描述结果的枚举组合方法相比，分析组合方法旨在获得渐近公式。
		
		\subsection{分区理论}
		分区理论研究了与整数分区有关的各种枚举和渐近问题，与q序列，特殊函数和正交多项式密切相关。原来是数论和分析的一部分，它现在被认为是组合学或独立领域的一部分。它在分析和解析数论中结合了双射线方法和各种工具，并与统计力学有联系。
		
		\subsection{图论}
		图是组合的基本对象。问题的范围从计算（例如，n个顶点上有k个边的图的数目）到结构（例如哪个图包含哈密尔顿周期）到代数问题（例如给定图G和两个数x和y，Tutte多项式TG（x，y）有一个组合解释？）。虽然图论与组合学之间有很强的联系，但这两者有时被认为是不同的主题。这是因为组合方法适用于许多图论问题，这两者通常用于寻求解决不同的问题。
		
		\subsection{设计理论}
		设计理论是组合设计的一个研究，它是具有一定相交属性的子集的集合。块设计是特殊类型的组合设计。这个领域是组合学中最古老的部分之一，如1850年提出的柯克曼的女学生问题。问题的解决是一个斯坦纳系统的特例，这个系统在有限简单群体的分类中扮演着重要的角色。该领域还与编码理论和几何组合相关。
		
		\subsection{有限几何}
		有限几何学是研究只有有限数量的点的几何系统。结构类似于连续几何（欧几里德平面，实际投影空间等）中所发现的，但组合定义的结构是所研究的主要项目。这个领域为设计理论提供了丰富的例子。它不应该与离散几何（组合几何）混淆。
		
		\subsection{秩序理论}
		秩序理论是对有限和无限的部分有序集合的研究。部分顺序的各种例子出现在代数，几何，数论，整个组合和图论中。值得注意的类和部分命令的例子包括格和布尔代数。
		
		\subsection{拟阵理论}
		拟阵理论抽象几何的一部分。它研究向量空间中向量集合（通常是有限集合）的属性，它不依赖于线性依赖关系中的特定系数。不仅结构而且枚举性质属于拟阵理论。哈特勒·惠特尼（Hassler Whitney）介绍了拟阵理论，并将其作为秩序理论的一部分进行了研究。它现在是一个独立的研究领域，与组合的其他部分有许多联系。
		
		\subsection{极值组合}
		极值组合研究集合系统的极值问题。在这种情况下提出的问题的类型是关于满足某些属性的最大可能图。例如，2n顶点上最大的无三角形图是一个完整的二部图Kn，n。通常很难找到极值的答案f（n），只能给出一个渐近估计。
		
		拉姆齐理论是极端组合的另一部分。它指出，任何足够大的配置将包含某种顺序。这是鸽子原理的一种高级概括。
		
		\subsection{概率组合}
		在概率组合中，问题的类型如下：随机离散对象（如随机图）的某个特性的概率是多少？例如，随机图中三角形的平均数是多少？概率方法也被用来确定具有某些规定属性的组合对象的存在（对于这些属性，显式的例子可能很难找到），只需要观察随机选择一个具有这些属性的对象的概率大于0.这种方法（通常被称为的概率方法）被证明非常有效的应用到极值组合数学和图论。密切相关的领域是有限马尔可夫链的研究特别是在组合对象上。这里再次使用概率工具来估计混合时间。
		
		通常与保罗·埃尔多斯（PaulErdős）有过关于这一主题的开拓性工作，传统上把概率组合学看作是一组工具来研究其他组合的问题。然而，随着应用的增长的算法分析，在计算机科学，以及古典概率，添加剂和概率数论，该地区最近发展成为组合数学的一个独立的领域。
		
		\subsection{代数组合}
		代数组合是一个数学领域，在各种组合环境中采用抽象代数的方法，特别是群论和表示论，相反地，将组合技术应用于代数问题。代数组合在其主题和技术上不断扩大其范围，可以看作是组合和代数方法之间相互作用特别强大和重要的数学领域。
		
		\subsection{几何组合}
		几何组合与凸和离散几何有关，特别是多面体组合。例如，它询问多少个凸多面体可以具有多少个面。多面体的度量性质也起着重要的作用，例如关于凸多面体刚度的Cauchy定理。也考虑特殊的多面体，如permutohedra，associahedra和Birkhoff多形体。我们应该注意到组合几何对于离散几何来说是一个老式的名字。
		
		\subsection{拓扑组合}
		概念和拓扑方法的组合模拟用于研究图着色，公平划分，分区，部分有序集，决策树，项链问题和离散莫尔斯理论。它不应该与代数拓扑的老名字的组合拓扑相混淆。
		
		\subsection{算术组合}
		算术组合出现在数论，组合，遍历理论和谐波分析之间的相互作用之中。它是关于与算术运算相关的组合估计（加法，减法，乘法和除法）。添加数论（有时也称为加性组合）是指仅涉及加减运算的特例。在算术组合学的一个重要技术是遍历理论的动力系统。
		
		\section{相关领域}
		\subsection{组合优化}
		组合优化是对离散和组合对象进行优化的研究。它起初是组合学和图论的一部分，但现在被视为应用数学和计算机科学的一个分支，涉及到运算研究，算法理论和计算复杂性理论。
		
		\subsection{编码理论}
		编码理论作为设计理论的一部分，以纠错码的早期组合结构开始。本课题的主要思想是设计高效可靠的数据传输方法。它现在是一个大的研究领域，是信息论的一部分。
		
		\subsection{离散和计算几何}
		离散几何（也称为组合几何）也开始作为组合的一部分，在凸多面体和接吻数字上有早期的结果。随着离散几何学应用于计算几何学的出现，这两个领域部分合并，成为一个独立的研究领域。与几何和拓扑组合学仍然有许多联系，它们本身可以被看作是早期离散几何的产物。
		
		\subsection{组合和动力系统}
		动力系统的组合方面是另一个新兴领域。这里可以在组合对象上定义动态系统。见例如图动力系统。
		
		\subsection{组合和物理学}
		组合和物理之间的相互作用越来越多，尤其是统计物理学。例子包括Ising模型的精确解，以及Potts模型与色谱和Tutte多项式之间的联系。
		
		\section{贡献者}
		王海侠 - 副教授 - 南京理工大学
		